package com.leetcode.algorithm.y22.m09.w2;

import java.util.Arrays;

/**
 * 57. 插入区间
 * 
 * https://leetcode.cn/problems/insert-interval/
 * 
 * @author jie.deng
 *
 */
class Question0057Solution01 {

	public int[][] insert(int[][] intervals, int[] newInterval) {
		int len = intervals.length;
		if (len == 0) {
			return new int[][] { newInterval };
		}
		int[][] ans = new int[len + 1][2];
		if (newInterval[1] < intervals[0][0]) {
			ans[0] = newInterval;
			for (int i = 0; i < len; i++) {
				ans[i + 1] = intervals[i];
			}
			return ans;
		}
		if (newInterval[0] > intervals[len - 1][1]) {
			for (int i = 0; i < len; i++) {
				ans[i] = intervals[i];
			}
			ans[len] = newInterval;
			return ans;
		}

		int idx = 0;
		int i = 0;
		while (idx < len && intervals[idx][1] < newInterval[0]) {
			ans[i++] = intervals[idx];
			idx++;
		}
		int left = Math.min(intervals[idx][0], newInterval[0]);
		while (idx < len && intervals[idx][0] <= newInterval[1]) {
			idx++;
		}
		ans[i++] = new int[] { left, Math.max(intervals[idx - 1][1], newInterval[1]) };
		while (idx < len) {
			ans[i++] = intervals[idx++];
		}
		return Arrays.copyOfRange(ans, 0, i);
	}
	
}